#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;  // 元素类型，假设为整型

typedef struct CSLinklist {
    ElemType data;          // 数据元素内容
    struct CSLinklist *firstchild;  // 指向该结点第一个孩子的指针
    struct CSLinklist *nextsibling; // 指向该结点下一个兄弟的指针
} CSLinklist, *CSTree;

// 创建新节点的函数
CSTree CreateNode(ElemType data) {
    CSTree newNode = (CSTree)malloc(sizeof(CSLinklist));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(-1);
    }
    newNode->data = data;
    newNode->firstchild = newNode->nextsibling = NULL;
    return newNode;
}

// 插入成员的函数
void InsertMember(CSTree *root, ElemType parentData, ElemType childData) {
    if (*root == NULL) {
        *root = CreateNode(parentData);
    }

    CSTree current = *root;
    while (current != NULL) {
        if (current->data == parentData) {
            CSTree newChild = CreateNode(childData);
            if (current->firstchild == NULL) {
                current->firstchild = newChild;
            } else {
                CSTree sibling = current->firstchild;
                while (sibling->nextsibling != NULL) {
                    sibling = sibling->nextsibling;
                }
                sibling->nextsibling = newChild;
            }
            return;
        }
        if (current->firstchild != NULL) {
            InsertMember(&current->firstchild, parentData, childData);
        }
        current = current->nextsibling;
    }
}

// 查找成员的函数
CSTree FindMember(CSTree root, ElemType data) {
    if (root == NULL) {
        return NULL;
    }
    if (root->data == data) {
        return root;
    }
    CSTree found = FindMember(root->firstchild, data);
    if (found != NULL) {
        return found;
    }
    return FindMember(root->nextsibling, data);
}

// 查看祖先的函数
void ViewAncestors(CSTree root, ElemType data) {
    if (root == NULL) {
        return;
    }
    if (FindMember(root, data) != NULL) {
        printf("%d ", root->data);
        ViewAncestors(root->firstchild, data);
    }
    ViewAncestors(root->nextsibling, data);
}

// 查看子孙的函数
void ViewDescendants(CSTree root, ElemType data) {
    if (root == NULL) {
        return;
    }
    if (root->data == data) {
        CSTree child = root->firstchild;
        while (child != NULL) {
            printf("%d ", child->data);
            ViewDescendants(child, child->data);
            child = child->nextsibling;
        }
    } else {
        ViewDescendants(root->firstchild, data);
        ViewDescendants(root->nextsibling, data);
    }
}

// 删除成员的函数
void DeleteMember(CSTree *root, ElemType data) {
    if (*root == NULL) {
        return;
    }

    if ((*root)->data == data) {
        CSTree temp = *root;
        *root = (*root)->nextsibling;
        free(temp);
        printf("删除节点 %d\n", data);
        return;
    }

    CSTree current = *root;
    while (current != NULL) {
        if (current->firstchild != NULL) {
            if (current->firstchild->data == data) {
                CSTree temp = current->firstchild;
                current->firstchild = current->firstchild->nextsibling;
                free(temp);
                printf("删除节点 %d\n", data);
                return;
            }
            DeleteMember(&current->firstchild, data);
        }
        if (current->nextsibling != NULL) {
            if (current->nextsibling->data == data) {
                CSTree temp = current->nextsibling;
                current->nextsibling = current->nextsibling->nextsibling;
                free(temp);
                printf("删除节点 %d\n", data);
                return;
            }
            DeleteMember(&current->nextsibling, data);
        }
        current = current->nextsibling;
    }
}

//验证
void VerifyTree(CSTree root, ElemType data) {
    if (FindMember(root, data) != NULL) {
        printf("警告: 节点 %d 仍然存在于树中\n", data);
    } else {
        printf("节点 %d 已成功删除\n", data);
    }
}

// 从键盘输入插入成员的函数
void InsertMembersFromKeyboard(CSTree *root) {
    int parentData, childData;
    char continueInput;

    do {
        printf("请输入父节点的数据: ");
        scanf("%d", &parentData);
        printf("请输入子节点的数据: ");
        scanf("%d", &childData);
        InsertMember(root, parentData, childData);

        printf("是否继续输入 (y/n): ");
        scanf(" %c", &continueInput);  // 注意这里有一个空格，用于吃掉前面的换行符
    } while (continueInput == 'y' || continueInput == 'Y');
}

void ClearInputBuffer() {
    while (getchar() != '\n');  // 读取并丢弃所有输入直到换行符
}


void Pause() {
    printf("按任意键继续...");
    getchar();
}

// 清屏函数
void ClearScreen() {
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif
}

// 显示菜单
void ShowMenu() {
    printf("家谱管理系统\n");
    printf("1. 插入成员\n");
    printf("2. 查看祖先\n");
    printf("3. 查看子孙\n");
    printf("4. 删除成员\n");
    printf("0. 退出程序\n");
    printf("请选择操作: ");
}

int main() {
    CSTree root = NULL;
    int choice;

    while (1) {
        ShowMenu();
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                InsertMembersFromKeyboard(&root);
                Pause();
                break;
            case 2: {
                int memberData;
                printf("请输入要查看祖先的成员数据: ");
                scanf("%d", &memberData);
                ClearInputBuffer();
                printf("成员 %d 的祖先: ", memberData);
                ViewAncestors(root, memberData);
                printf("\n");
                Pause();
                break;
            }
            case 3: {
                int memberData;
                printf("请输入要查看子孙的成员数据: ");
                scanf("%d", &memberData);
                ClearInputBuffer();
                printf("成员 %d 的子孙: ", memberData);
                ViewDescendants(root, memberData);
                printf("\n");
                Pause();
                break;
            }
            case 4: {
                int memberData;
                printf("请输入要删除的成员数据: ");
                scanf("%d", &memberData);
                ClearInputBuffer();
                DeleteMember(&root, memberData);
                VerifyTree(root, memberData);  // 验证删除操作
                printf("成员 %d 已删除\n", memberData);
                Pause();
                break;
            }            
            case 0: {
                printf("退出程序\n");
                Pause();
                return 0;
            }
            default: {
                printf("无效的选择，请重新输入\n");
                Pause();
            }
        }
        // 操作完成后清屏
        ClearScreen();
    }

    return 0;
}      